/*
提交链接：https://leetcode.cn/problems/house-robber/submissions/562541683https://leetcode.cn/problems/house-robber/submissions/562541683
198. 打家劫舍-中等
完成日期：2024/9/8
线性dp
*/

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;// 如果房屋列表为空，则不能偷窃任何金额
        if (nums.size() == 1) return nums[0]; // 如果只有一间房屋，直接返回这间房屋的金额
        if (nums.size() == 2) return max(nums[0], nums[1]);// 如果有两间房屋，选择金额较大的那一间
        vector<int> dp(nums.size());// 创建一个动态规划数组 dp
        // 初始化 dp 数组的前两个值
        dp[0] = nums[0];  // 只有一间房屋时，最大金额就是这间房屋的金额
        dp[1] = max(nums[0], nums[1]);  // 两间房屋时，选择金额较大的房屋
        for (size_t i = 2; i < nums.size(); ++i) {// 从第三间房屋开始，逐步计算最大偷窃金额
            // dp[i] 代表偷窃前 i+1 间房屋的最大金额
            // 选择不偷窃第 i 间房屋（dp[i-1]），或偷窃第 i 间房屋（dp[i-2] + nums[i]）
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        // 返回最终的结果，表示偷窃所有房屋中可以获得的最大金额
        return dp[nums.size()-1];
    }
};